package org.example.code.test2024.eleven;

import java.util.*;

/**
 * @Title: test1125
 * @Author yxy
 * @Package org.example.code.eleven
 * @Date 2024/11/25 09:38
 * @description:
 */
public class test1125 {

    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        if (s.length() < 10) return result;
        Map<String, Integer> sequenceCount = new HashMap<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            String subSequence = s.substring(i, i + 10);
            sequenceCount.put(subSequence, sequenceCount.getOrDefault(subSequence, 0) + 1);
        }
        for (Map.Entry<String, Integer> entry : sequenceCount.entrySet()) {
            if (entry.getValue() > 1) {
                result.add(entry.getKey());
            }
        }
        return result;
    }


    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])&&Math.abs(i-map.get(nums[i]))<=k){
                return true;
            }
            map.put(nums[i],i);
        }
        return false;
    }

    /**
     * 中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；
     * 此时中位数是最中间的两个数的平均数。
     * 例如：[2,3,4]，中位数是 3
     * [2,3]，中位数是 (2 + 3) / 2 = 2.5
     * 给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。
     * 窗口中有 k 个数，每次窗口向右移动 1 位。
     * 你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
     * @param nums
     * @param k
     * @return
     */
    public double[] medianSlidingWindow(int[] nums, int k) {
        List<Double> result = new ArrayList<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i=0;i<nums.length;i++){
            if (maxHeap.isEmpty() || nums[i] <= maxHeap.peek()) {
                maxHeap.offer(nums[i]);
            } else {
                minHeap.offer(nums[i]);
            }
            balanceHeaps(maxHeap, minHeap);
            if (i >= k - 1) {
                result.add(getMedian(maxHeap, minHeap, k));
                int toRemove = nums[i - k + 1];
                if (toRemove <= maxHeap.peek()) {
                    maxHeap.remove(toRemove);
                } else {
                    minHeap.remove(toRemove);
                }
                balanceHeaps(maxHeap, minHeap);
            }
        }
        double[] res = new double[result.size()];
        for(int i=0;i<result.size();i++){
            res[i] = result.get(i);
        }
        return res;
    }

    private void balanceHeaps(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        while (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        }
        while (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    private double getMedian(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap, int k) {
        if (k % 2 == 0) {
            return ((double) maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }



    public static void main(String[] args) {
        test1125 test = new test1125();
        int[] nums = new int[]{2147483647,2147483647};
        double[] doubles = test.medianSlidingWindow(nums, 2);
        for (int i = 0; i < doubles.length; i++) {
            System.out.println(doubles[i]);
        }
    }
}
